'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-09-08 14:55:16
LastEditTime: 2025-09-08 15:03:42
'''


class Solution:

    def minPathSum(self, grid):

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == j == 0:
                    continue

                elif i == 0:
                    grid[i][j] = grid[i][j - 1] + grid[i][j]
                elif j == 0:
                    grid[i][j] = grid[i - 1][j] + grid[i][j]

                else:
                    grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j - 1])

        
        return grid[-1][-1]


if __name__ == "__main__":
    
    grid = [[1,3,1],[1,5,1],[4,2,1]]
    sol = Solution()

    res = sol.minPathSum(grid)
    print(res)




